import Excepetion.IndexExcepetion;

public class SingleList {

    //定义单链表的节点(静态内部内)
    static class note{
        public int val; //每一个结点的数值域
        private note next; //记录下一个节点的地址
        //提供节点数值域的构造方法，不用提供next构造方法的原因是因为不能确定每个节点的下一个节点的值
        public note(int val) {
            this.val = val;
        }

        public note() {
        }
    }

    //定义单链表的头节点
    public note head;

    //创建一个单链表(非正规初学演示)
    public void create(){
        note note1=new note(1);
        note note2=new note(5);
        note note3=new note(3);
        note note4=new note(4);
        note note5=new note(2);
        note note6=new note(6);
        head=note1;
        note1.next=note2;
        note2.next=note3;
        note3.next=note4;
        note4.next=note5;
        note5.next=note6;
    }

    //打印链表的元素
    public void display(){
        note cur=head;
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println("");
    }

    //用于打印合并链表后的
    public static void display(note head){
        note cur=head;
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println("");
    }

    //单链表元素的插入(头插法)
    public void headInsert(int data){
        note insert=new note(data);
        insert.next=head;
        head=insert;
    }

    //单链表元素的尾插(尾插法)
    public void lastInsert(int data){
        note insert=new note(data);
        note cur=head;
        if(head==null){
            headInsert(data);
            return;
        }
        while(cur.next!=null){
            cur=cur.next;
        }
        cur.next=insert;
    }

    //中间指定下标插入数据
    public void indexInsert(int index,int data){
        //检查下标合法性
        checkIndex(index);
        //检查是否为头插
        if(index==0){
            headInsert(data);
            return;
        }
        //检查是否为尾插
        if(index==size()){
            lastInsert(data);
            return;
        }
        //链表中间下标位置数据插入
        note cur=head;
        note insert=new note(data);
        note preNote=findIndex(index);
        insert.next=preNote.next;
        preNote.next=insert;
    }

    //计算单链表长度
    public int size(){
        if(head==null){
            System.out.println("该链表无元素");
            return 0;
        }
        note cur=head;
        int lenth=1;
        while(cur.next!=null){
            lenth++;
            cur=cur.next;
        }
        return lenth;
    }

    //下标合法性检查
    public void checkIndex(int index){
        if(index<0||index>size()){
            throw new IndexExcepetion("输入的下标不合法");
        }
    }

    //找到下标index前一个的节点
    public note findIndex(int index){
        note cur=head;
        while(index-1!=0){
            cur=cur.next;
            index--;
        }
        return cur;
    }



    //查找链表中是否存在key值
    public boolean contain(int key){
        note cur=head;
        if(cur==head&&cur.val==key){
            System.out.println("找到了，该值在头节点上");
            return true;
        }
        while(cur.next!=null){
            if(cur.next.val==key){
                System.out.println("找到了");
                return true;
            }
            cur=cur.next;
        }
        System.out.println("没找到");
        return false;
    }

    //删除链表中第一次出现的key值
    public void delectFirstKey(int key){
        if(contain(key)){
            note cur=head;
            if(cur==head&&cur.val==key){
                System.out.println("已删除");
                head=cur.next;
                return;
            }
            while(cur.next!=null){
                if(cur.next.val==key){
                    cur.next=cur.next.next;
                    System.out.println("已删除");
                    return;
                }
                cur=cur.next;
            }
        }
        System.out.println("该key值未找到");
    }

    //删除链表中所有出现的key值
    public  note deleteAllKey(int key){
        if(head==null){
            return null;
        }
        note cur=head;
        note curNext=head.next;
        //while循环用于删除除头节点以外的节点是否为key值
        while(curNext!=null){
            if(curNext.val==key){
                cur.next=curNext.next;
                curNext=curNext.next;
            }else{
                cur=curNext;
                curNext=curNext.next;
            }
        }
        //最后判断头节点是否为key值
        if(head.val==key){
            head=head.next;
        }
        return head;
    }

    //反转链表
    public note reverse(){
        if(head==null){
            return null;
        }
        if(head.next==null){
            return head;
        }
        note head1=head;
        note cur=head.next;
        while(cur!=null){
            note curNext=cur.next;
            cur.next=head;
            head=cur;
            cur=curNext;
        }
        head1.next=null;
        return head;
    }

    //返回链表的中间节点，奇数个节点返回中间节点，偶数个节点返回第二个节点
    //方法：利用快慢指针的方法
    public note findMiddleNote(note head1){
        if(head1==null){
            return null;
        }
        if(head1.next==null){
            return head1;
        }
        note fast=head1;
        note slow=head1;
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        return slow;
    }

    //输入一个链表，输出该链表中倒数第k个结点
    //方法：快慢指针
    public note findReciprocal(int k){
        if(k<=0){
            return null;
        }
        if(head==null){
            return null;
        }
        note fast=head;
        note slow=head;
        //先让快指针走k-1步
        while(k-1>0){
            //判断k值是否超出给定链表的长度
            if(fast==null){
                return null;
            }
            fast=fast.next;
            k--;
        }
        //快慢指针以同样的速度移动，最后慢指针指向的节点就是目标节点
        while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }

    // 将两个有序链表合并为一个新的有序链表并返回。
    public note mergeList(note head1,note head2){
        //判断两个链表存在空链表的情况
        if(head1==null){
            return head2;
        }
        if(head2==null){
            return head1;
        }
        note newHead=new note();//创建一个傀儡头节点，存放合并后链表的头节点
        note minTemp=newHead;//用于存放val值较小的节点
        //合并链表
        while(head1!=null&&head2!=null){
            if(head1.val>=head2.val){
                minTemp.next=head2;
                minTemp=head2;
                head2=head2.next;
            }else{
                minTemp.next=head1;
                minTemp=head1;
                head1=head1.next;
            }

        }
        //判断并合并较长的那一个链表的剩余部分
        if(head1==null){
            minTemp.next=head2;
        }
        if(head2==null){
            minTemp.next=head1;
        }
        return newHead.next;

    }

    //给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前(且保持原顺序不变)
    //方法：将链表中小于x的部分和大于x的部分分别放在两个不同的临时(左右)链表中，最后判断左右链表并合并链表
    public note splitX(int x){
        if(head==null){
            return null;
        }
        note cur=head;
        //用于存放小于x的节点部分(右)
        note rBegain=null;
        note rEnd=null;
        //用于存放大于x的节点部分(左)
        note lBegain=null;
        note lEnd=null;
        //遍历链表并进行左右链表的存放
        while(cur!=null){
            //小于x的节点临时链表
            if(cur.val>=x){
                //（右临时链表）第一次插入节点
                if(rBegain==null){
                    rBegain=cur;
                    rEnd=cur;
                }else{
                    rEnd.next=cur;
                    rEnd=rEnd.next;
                }

            }
            //大于X节点部分的临时链表
            if(cur.val<x){
                //（左临时链表）第一次插入节点
                if(lBegain==null){
                    lBegain=cur;
                    lEnd=cur;
                }else{
                    lEnd.next=cur;
                    lEnd=lEnd.next;
                }

            }
            cur=cur.next;
        }

        //判断左右临时来链表是否有空链表，返回该非空链表的头节点
        if(rBegain==null){
            lEnd.next=null;//确保返回链表的最后一个节点next值为null;
            return lBegain;
        }
        if(lBegain==null){
            rEnd.next=null;//确保返回链表的最后一个节点next值为null;
            return rBegain;
        }

        //左右临时链表都不为空的情况
        rEnd.next=null;//确保右链表最后一个节点next值为null
        lEnd.next=rBegain;//连接左右临时链表
        return lBegain;

    }


    //可见第八题
    //输入两个链表，找出它们公共部分的第一个公共结点。YYYYY
    //
    public note sameNote(note head1,note head2){
        if(head1==null||head2==null){
            return null;
        }
        note cur1=head1;//用于储存较长链表的
        note cur2=head2;//用于储存较短链表的
        int lenth1=0;
        int lenth2=0;
        //分别求两个链表的长度
        while(cur1!=null){
            lenth1++;
            cur1=cur1.next;
        }
        while(cur2!=null){
            lenth2++;
            cur2=cur2.next;
        }
        cur1=head1;
        cur2=head2;
        //确保cur储存的是长链表且lenth1为长链表的长度
        if(lenth1<lenth2){
            cur1=head2;
            cur2=head1;
            int index=lenth1;
            lenth1=lenth2;
            lenth2=index;
        }
        //长链表先走lenth1-lenth2步，然后再同步判断节点是否相同
        int k=lenth1-lenth2;
        while(k!=0){
            cur1=cur1.next;
            k--;
        }
        //判断从相同数目节点处，后面的每个节点引用是否都相同（Y）

        while(cur1!=cur2&&cur1!=null){

            cur1=cur1.next;
            cur2=cur2.next;
        }

        if(cur1==null||cur2==null){
            return null;
        }
        return cur1;
    }

    //给定一个链表，判断链表中是否有环
    //课表第九题
    public boolean hasCircle(note head) {
        if (head == null || head.next == null) {
            return false;
        }
        note slow = head;
        note fast = head.next;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }

        }
        return false;
    }

        //给定一个链表，判断链表中是否有环,并返回这个环的入口点
        //课表第十题
    public note circleNote(note head){
        if (head == null || head.next == null) {
            return null;
        }
        note slow = head;
        note fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;
            }

        }

        slow=head;
        while(slow!=fast){
            fast=fast.next;
            slow=slow.next;
        }
        if(fast==null||slow==null){
            return null;
        }
        return slow;
    }

    //判断一个链表是否是回文链表
    //方法：第一步判断单向链表是否为空，找到单向链表的中点下标
    //从该位置进行链表的反转(分割为左右两个子链表)
    //将两分割好的两个子链表进行比较
    public boolean isPalindrome(note head){
        if(head==null){
            return false;
        }
        //只有一个节点的回文情况
        if(head.next==null){
            return true;
        }
        //寻找链表中间节点
        note fast=head;
        note slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        //反转后面部分的链表
        note cur=slow.next;
        while(cur!=null){
            note curNext=cur.next;
            cur.next=slow;
            slow=cur;
            cur=curNext;
        }
        //回文判断
        while(head!=slow&&slow.next!=null){
            if(head.val!=slow.val){
                return false;
            }
            if(head.next==slow&&head.val==slow.val){
                return true;
            }

            head=head.next;
            slow=slow.next;
        }

        return true;


    }
}